% LaTeX source for textbook ``How to think like a computer scientist''
% Copyright (c)  2001  Allen B. Downey, Jeffrey Elkner, and Chris Meyers.

% Permission is granted to copy, distribute and/or modify this
% document under the terms of the GNU Free Documentation License,
% Version 1.1  or any later version published by the Free Software
% Foundation; with the Invariant Sections being "Contributor List",
% with no Front-Cover Texts, and with no Back-Cover Texts. A copy of
% the license is included in the section entitled "GNU Free
% Documentation License".

% This distribution includes a file named fdl.tex that contains the text
% of the GNU Free Documentation License.  If it is missing, you can obtain
% it from www.gnu.org or by writing to the Free Software Foundation,
% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

\chapter{Sets of objects}

\section{Composition}
\index{composition}
\index{nested structure}

By now, you have seen several examples of composition.
One of the
first examples was using a method invocation as part of an
expression.  Another example is the nested structure of statements;
you can put an {\tt if} statement within a {\tt while} loop, within
another {\tt if} statement, and so on.

Having seen this pattern, and having learned about lists and objects,
you should not be surprised to learn that you can create lists of
objects.  You can also create objects that contain lists (as
attributes); you can create lists that contain lists; you can
create objects that contain objects; and so on.

In this chapter and the next, we will look at some examples of these
combinations, using {\tt Card} objects as an example.


\section{{\tt Card} objects}
\index{Card}
\index{class!Card}

If you are not familiar with common playing cards, now would be a good
time to get a deck, or else this chapter might not make much sense.
There are fifty-two cards in a deck, each of which belongs to one of four
suits and one of thirteen ranks.  The suits are Spades, Hearts, Diamonds, and
Clubs (in descending order in bridge).  The ranks are Ace, 2, 3, 4, 5,
6, 7, 8, 9, 10, Jack, Queen, and King.  Depending on the game that you are
playing, the rank of Ace may be higher than King or lower than 2.

\index{rank}
\index{suit}

If we want to define a new object to represent a playing card, it is
obvious what the attributes should be: {\tt rank} and
{\tt suit}.  It is not as obvious what type the attributes
should be.  One possibility is to use strings containing words like
{\tt "Spade"} for suits and {\tt "Queen"} for ranks.  One problem with
this implementation is that it would not be easy to compare cards to
see which had a higher rank or suit.

\index{encode}
\index{encrypt}
\index{map to}

An alternative is to use integers to {\bf encode} the ranks and suits.
By ``encode,'' we do not mean what some people think, which is to
encrypt or translate into a secret code.  What a computer scientist
means by ``encode'' is ``to define a mapping between a
sequence of numbers and the items I want to represent.'' For example:

\beforefig
\begin{tabular}{l c l}
Spades & $\mapsto$ & 3 \\
Hearts & $\mapsto$ & 2 \\
Diamonds & $\mapsto$ & 1 \\
Clubs & $\mapsto$ & 0
\end{tabular}
\afterfig

An obvious feature of this mapping is that the suits map to integers in
order, so we can compare suits by comparing integers.  The mapping for
ranks is fairly obvious; each of the numerical ranks maps to the
corresponding integer, and for face cards:

\beforefig
\begin{tabular}{l c l}
Jack & $\mapsto$ & 11 \\
Queen & $\mapsto$ & 12 \\
King & $\mapsto$ & 13 \\
\end{tabular}
\afterfig

The reason we are using mathematical notation for these mappings is
that they are not part of the Python program.  They are part of the
program design, but they never appear explicitly in the code.  The
class definition for the {\tt Card} type looks like this:

\beforeverb
\begin{verbatim}
class Card:
  def __init__(self, suit=0, rank=2):
    self.suit = suit
    self.rank = rank
\end{verbatim}
\afterverb
%
As usual, we provide an initialization method that takes an optional
parameter for each attribute.  The default value of {\tt suit} is
0, which represents Clubs.

\index{constructor}

To create a Card, we invoke the Card constructor with the
suit and rank of the card we want.

\beforeverb
\begin{verbatim}
threeOfClubs = Card(3, 1)
\end{verbatim}
\afterverb
%
In the next section we'll figure out which card we just made.


\section{Class attributes and the {\tt \_\_str\_\_} method}
\index{class attribute}
\index{attribute!class}

In order to print {\tt Card} objects in a way that people can easily
read, we want to map the integer codes onto words.  A natural way to
do that is with lists of strings.  We assign these lists to {\bf class
attributes} at the top of the class definition:

\beforeverb
\begin{verbatim}
class Card:
  suitList = ["Clubs", "Diamonds", "Hearts", "Spades"]
  rankList = ["narf", "Ace", "2", "3", "4", "5", "6", "7", 
              "8", "9", "10", "Jack", "Queen", "King"]

  #init method omitted

  def __str__(self):
    return (self.rankList[self.rank] + " of " + 
            self.suitList[self.suit])
\end{verbatim}
\afterverb
%
A class attribute is defined outside of any method, and it can be
accessed from any of the methods in the class.

Inside {\tt \_\_str\_\_}, we can use {\tt suitList} and {\tt rankList}
to map the numerical values of {\tt suit} and {\tt rank} to strings.
For example, the expression \verb+self.suitList[self.suit]+ means
``use the attribute {\tt suit} from the object {\tt self} as an index
into the class attribute named {\tt suitList}, and select the
appropriate string.''

The reason for the {\tt "narf"} in the first element in {\tt
rankList} is to act as a place keeper for the zero-eth element of the
list, which should never be used.  The only valid ranks are 1 to 13.  This
wasted item is not entirely necessary.  We could have started at 0,
as usual, but it is less confusing to encode 2 as 2, 3 as 3, and so on.

With the methods we have so far, we can create and print cards:

\beforeverb
\begin{verbatim}
>>> card1 = Card(1, 11)
>>> print card1
Jack of Diamonds
\end{verbatim}
\afterverb
%
Class attributes like {\tt suitList} are shared by all {\tt Card}
objects.  The advantage of this is that we can use any {\tt Card}
object to access the class attributes:

\beforeverb
\begin{verbatim}
>>> card2 = Card(1, 3)
>>> print card2
3 of Diamonds
>>> print card2.suitList[1]
Diamonds
\end{verbatim}
\afterverb
%
The disadvantage is that if we modify a class attribute, it
affects every instance of the class.  For example, if we decide
that ``Jack of Diamonds'' should really be called
``Jack of Swirly Whales,'' we could do this:

\index{instance!object}
\index{object instance}

\beforeverb
\begin{verbatim}
>>> card1.suitList[1] = "Swirly Whales"
>>> print card1
Jack of Swirly Whales
\end{verbatim}
\afterverb
%
The problem is that {\em all} of the Diamonds just became
Swirly Whales:

\beforeverb
\begin{verbatim}
>>> print card2
3 of Swirly Whales
\end{verbatim}
\afterverb
%
It is usually not a good idea to modify class attributes.



\section{Comparing cards}
\label{comparecard}
\index{operator!conditional}
\index{conditional operator}

For primitive types, there are conditional operators
({\tt <}, {\tt >}, {\tt ==}, etc.)
that compare
values and determine when one is greater than, less than, or equal to
another.  For user-defined types, we can override the behavior of
the built-in operators by providing a method named
{\tt \_\_cmp\_\_}.  By convention, {\tt \_\_cmp\_\_}
has two parameters, {\tt self} and {\tt other}, and returns
1 if the first object is greater, -1 if the
second object is greater, and 0 if they are equal to each other.

\index{override}
\index{operator overloading}
\index{ordering}
\index{complete ordering}
\index{partial ordering}

Some types are completely ordered, which means that you can compare
any two elements and tell which is bigger.  For example, the integers
and the floating-point numbers are completely ordered.  Some sets are
unordered, which means that there is no meaningful way to say that one
element is bigger than another.  For example, the fruits are
unordered, which is why you cannot compare apples and oranges.

The set of playing cards is partially ordered, which means that
sometimes you can compare cards and sometimes not.  For example, you
know that the 3 of Clubs is higher than the 2 of Clubs, and the 3 of
Diamonds is higher than the 3 of Clubs.  But which is better, the 3 of
Clubs or the 2 of Diamonds?  One has a higher rank, but the other has
a higher suit.

\index{comparable}

In order to make cards comparable, you have to decide which is more
important, rank or suit.  To be honest, the choice is
arbitrary.  For the sake of choosing, we will say that suit is more
important, because a new deck of cards comes sorted
with all the Clubs together, followed by all the Diamonds, and so on.

With that decided, we can write {\tt \_\_cmp\_\_}:

\beforeverb
\begin{verbatim}
def __cmp__(self, other):
  # check the suits
  if self.suit > other.suit: return 1
  if self.suit < other.suit: return -1
  # suits are the same... check ranks
  if self.rank > other.rank: return 1
  if self.rank < other.rank: return -1
  # ranks are the same... it's a tie
  return 0
\end{verbatim}
\afterverb
%
In this ordering, Aces appear lower than Deuces (2s).

\begin{quote}
{\em As an exercise, modify {\tt \_\_cmp\_\_} so that Aces are
ranked higher than Kings.}
\end{quote}


\section{Decks}
\index{list!of objects}
\index{object!list of}
\index{deck}

Now that we have objects to represent {\tt Card}s, the next logical
step is to define a class to represent a {\tt Deck}.  Of course, a
deck is made up of cards, so each {\tt Deck} object will contain a
list of cards as an attribute.

\index{initialization method}
\index{method!initialization}

The following is a class definition for the {\tt Deck} class.  The
initialization method creates the attribute {\tt cards} and generates
the standard set of fifty-two cards:

\index{composition}
\index{loop!nested}

\beforeverb
\begin{verbatim}
class Deck:
  def __init__(self):
    self.cards = []
    for suit in range(4):
      for rank in range(1, 14):
        self.cards.append(Card(suit, rank))
\end{verbatim}
\afterverb
%
The easiest way to populate the deck is with a nested loop.  The outer
loop enumerates the suits from 0 to 3.  The inner loop enumerates the
ranks from 1 to 13.  Since the outer loop iterates four times, and the
inner loop iterates thirteen times, the total number of times the body
is executed is fifty-two (thirteen times four).  Each iteration
creates a new instance of {\tt Card} with the current suit and rank,
and appends that card to the {\tt cards} list.

The {\tt append} method works on lists but not, of course, tuples.

\index{append method}
\index{list method}
\index{method!list}

\adjustpage{1}

\section{Printing the deck}
\label{printdeck}
\index{printing!deck object}


As usual, when we define a new type of object we want a method
that prints the contents of an object.
To print a {\tt Deck}, we traverse the list and print each {\tt Card}:

\beforeverb
\begin{verbatim}
class Deck:
  ...
  def printDeck(self):
    for card in self.cards:
      print card
\end{verbatim}
\afterverb
%
Here, and from now on, the ellipsis ({\tt ...}) indicates that we have
omitted the other methods in the class.

As an alternative to {\tt printDeck}, we could
write a {\tt \_\_str\_\_} method for the {\tt Deck} class.  The
advantage of {\tt \_\_str\_\_} is that it is more flexible.  Rather
than just printing the contents of the object, it generates a string
representation that other parts of the program can manipulate
before printing, or store for later use.

Here is a version of {\tt \_\_str\_\_} that returns a string
representation of a {\tt Deck}.
To add a bit of pizzazz, it arranges the cards in a cascade
where each card is indented one space more than the previous card:

\beforeverb
\begin{verbatim}
class Deck:
  ...
  def __str__(self):
    s = ""
    for i in range(len(self.cards)):
      s = s + " "*i + str(self.cards[i]) + "\n"
    return s
\end{verbatim}
\afterverb
%
This example demonstrates several features.  First, instead of
traversing {\tt self.cards} and assigning each card to a variable,
we are using {\tt i} as a loop
variable and an index into the list of cards.

Second, we are using the string multiplication operator to indent
each card by one more space than the last.  The expression
{\tt " "*i} yields a number of spaces equal to the current value
of {\tt i}.

Third, instead of using the {\tt print} command to print the cards,
we use the {\tt str} function.  Passing an object as an argument to
{\tt str} is equivalent to invoking the {\tt \_\_str\_\_} method on
the object.

\index{accumulator}

Finally, we are using the variable {\tt s} as an {\bf accumulator}.
Initially, {\tt s} is the empty string.  Each time through the loop, a
new string is generated and concatenated with the old value of {\tt s}
to get the new value.  When the loop ends, {\tt s} contains the
complete string representation of the {\tt Deck}, which looks like
this:

\adjustpage{-2}
\pagebreak

\beforeverb
\begin{verbatim}
>>> deck = Deck()
>>> print deck
Ace of Clubs
 2 of Clubs
  3 of Clubs
   4 of Clubs
    5 of Clubs
     6 of Clubs
      7 of Clubs
       8 of Clubs
        9 of Clubs
         10 of Clubs
          Jack of Clubs
           Queen of Clubs
            King of Clubs
             Ace of Diamonds
\end{verbatim}
\afterverb
%
And so on.  Even though the result appears on 52 lines, it is
one long string that contains newlines.


\section{Shuffling the deck}
\index{shuffle}

If a deck is perfectly shuffled, then any card is equally likely
to appear anywhere in the deck, and any location in the deck is
equally likely to contain any card.

\index{random}
\index{randrange}

To shuffle the deck, we will use the {\tt randrange} function
from the {\tt random} module.  With two integer arguments,
{\tt a} and {\tt b}, {\tt randrange} chooses a random integer in
the range {\tt a <= x < b}.  Since the upper bound is strictly
less than {\tt b}, we can use the length of a list as the
second argument, and we are guaranteed to get a legal index.
For example, this expression chooses the index of a random card in a deck:

\beforeverb
\begin{verbatim}
random.randrange(0, len(self.cards))
\end{verbatim}
\afterverb
%
An easy way to shuffle the deck is by traversing the cards and
swapping each card with a randomly chosen one.  It is possible that
the card will be swapped with itself, but that is fine.  In fact, if
we precluded that possibility, the order of the cards would be less
than entirely random:

\adjustpage{-2}
\pagebreak

\beforeverb
\begin{verbatim}
class Deck:
  ...
  def shuffle(self):
    import random
    nCards = len(self.cards)
    for i in range(nCards):
      j = random.randrange(i, nCards)
      self.cards[i], self.cards[j] = self.cards[j], self.cards[i]
\end{verbatim}
\afterverb
%
Rather than assume that there are fifty-two cards in the deck, we get
the actual length of the list and store it in {\tt nCards}.

\index{swap}
\index{tuple assignment}
\index{assignment!tuple}

For each card in the deck, we choose a random card from among the
cards that haven't been shuffled yet.  Then we swap the current
card ({\tt i}) with the selected card ({\tt j}).  To swap the
cards we use a tuple assignment, as in Section~\ref{tuple assignment}:

\beforeverb
\begin{verbatim}
self.cards[i], self.cards[j] = self.cards[j], self.cards[i]
\end{verbatim}
\afterverb
%
\begin{quote}
{\em As an exercise, rewrite this line of code
without using a sequence assignment.}
\end{quote}


\section{Removing and dealing cards}
\index{removing cards}

Another method that would be useful for the {\tt Deck} class is {\tt
removeCard}, which takes a card as an argument, removes it, and
returns {\tt True} if the card was in the deck and {\tt False}
otherwise:

\beforeverb
\begin{verbatim}
class Deck:
  ...
  def removeCard(self, card):
    if card in self.cards:
      self.cards.remove(card)
      return True
    else: 
      return False
\end{verbatim}
\afterverb
%
The {\tt in} operator returns true if the first operand is in the
second, which must be a list or a tuple.  If the first operand is an
object, Python uses the object's {\tt \_\_cmp\_\_} method to determine
equality with items in the list.  Since the {\tt \_\_cmp\_\_} in the
{\tt Card} class checks for deep equality, the {\tt removeCard} method
checks for deep equality.

\index{in operator}
\index{operator!in}

To deal cards, we want to remove and return the top card.
The list method {\tt pop} provides a convenient way to do that:

\beforeverb
\begin{verbatim}
class Deck:
  ...
  def popCard(self):
    return self.cards.pop()
\end{verbatim}
\afterverb
%
Actually, {\tt pop} removes the {\em last} card in the list, so we are in
effect dealing from the bottom of the deck.

\index{boolean function}
\index{function!boolean}

One more operation that we are likely to want is the boolean function
{\tt isEmpty}, which returns true if the deck contains no cards:

\beforeverb
\begin{verbatim}
class Deck:
  ...
  def isEmpty(self):
    return (len(self.cards) == 0)
\end{verbatim}
\afterverb


\section{Glossary}

\begin{description}

\item[encode:]  To represent one set of values using another
set of values by constructing a mapping between them.

\item[class attribute:] A variable that is defined inside
a class definition but outside any method.  Class attributes
are accessible from any method in the class and are shared
by all instances of the class.

\item[accumulator:] A variable used in a loop to accumulate
a series of values, such as by concatenating them onto
a string or adding them to a running sum.

\index{encode}
\index{class attribute}
\index{attribute!class}
\index{accumulator}

\end{description}
